The invention relates to the determination of the locations of multiple objects based on the measurements of multiple sensors. More particularly, the invention relates to determining by trilateration the locations of multiple objects detected by multiple, spaced range sensors.
Trilateration is the art of determining the location of an object in space based on knowledge of the range (distance) of the object from multiple known locations. For instance, knowledge of the range of an object from a known location (e.g., one particular sensor) defines a sphere on which the object must lie, that sphere being the sphere that is centered at the sensor and has a radius equal to the measured range value. A range value from two separate locations (sensors) defines two distinct spheres on which the object must lie. Accordingly, the object must lie on the locus of points defined by the intersection of the two spheres, which is a circle. If the range from a third location (or sensor) to the object is known, then the object is known to lie on the locus of points defined by the intersection of all three spheres. For many practical scenarios, the intersection of these three spheres defines a single point which locates the object.
As another example, in a two dimensional environment (or at least an environment that can be assumed to be two dimensional), range readings from only two sensors to the same object will define two circles that intersect at two points. For many practical scenarios, however, only one of these intersections will be located within the detection area of the sensors.
One example of a sensor that provides a range measurement, but no bearing measurement is a broad azimuth radar reflection system. As is well known in the related arts, one can send out a radio frequency (RF) beam from a known location and then receive reflections of that beam at the same (or another known) location and detect the time delay between the time the beam was issued and its reflection back to the sensor. The delay period can be converted to a round-trip distance by multiplying it by the speed of the waves.
Of course, if the radar beam has a defined azimuth, the radar detection system also provides at least some bearing information. Air traffic radar is a well known example of a radar that provides both range and bearing information. Such radars send out very narrow beams from a rotating transmitter antenna. Therefore, range can be determined from the delay of the reflected beam, while bearing can be determined from the angular orientation of the antenna at the time of the receipt of the reflected beam.
In actuality, virtually all radar systems give some bearing information because the transmitters rarely generate totally spherical wave fronts with a full 360xc2x0 azimuth. For instance, even a radar with an azimuth as wide as 180xc2x0 eliminates half of the bearing spectrum (assuming one knows the direction in which the sensor is facing).
In theory, when there is a single, point object in the field of view as assumed in the examples discussed above, trilateration is mathematically simple. However, real objects are not point objects. For instance, three sensors detecting the same object may detect slightly different surfaces of the object, wherein each surface is, essentially by definition, at a different location. Further, even in the case of an ideal point object, each sensor has some error range and thus each sensor reading will be inaccurate by some amount. Accordingly, in a real world situation, the three circles defined by the range readings from three different sensor of a single object may not, in fact, intersect at a single point. Rather, there may be three closely spaced intersection points of two circles each, i.e., first and second circles, first and third circles, and second and third circles. Accordingly, various algorithms have been developed for estimating an exact location based on such imperfect readings.
To further complicate matters, in a real world application, there typically will be more than one object in the field of view such that each sensor receives a plurality of reflected wave fronts and, therefore, a plurality of range readings.
Merely as an example, let us consider a highly simplified example in which four sensors each detect ten reflected wave fronts from the same ten actual objects. In this highly simplified example, this means that as many as 10xc3x9710xc3x9710xc3x9710=10,000 xe2x80x9cpotential objectsxe2x80x9d will be identified. Let us further assume that we will only consider objects to potentially exist where each of the four sensors has a range reading that defines a circle (or a sphere if a three dimensional system) that intersects a range circle from all three other sensors. It is likely that not all range readings (circles) of each sensor will intersect with the range readings of all three other sensors and, accordingly, with this assumption, it is likely that the number of potential objects will be substantially less than 10,000. However, the number of potential objects still could number in the hundreds in a realistic environment containing ten actual objects. Accordingly, practical trilateration algorithms should include a process for predicting those of the hundreds of potential objects in the field of view that represent actual objects and those that do not (those that correspond to xe2x80x9cfalse objectsxe2x80x9d). Ideally, such an algorithm should pare down the hundreds of xe2x80x9cpotential objectsxe2x80x9d to the ten xe2x80x9cactual objectsxe2x80x9d in the field of view.
Accordingly, it is an object of the present invention to provide an improved multi object location sensor method and apparatus.
It is a further object of the present invention to provide a method and apparatus for eliminating false objects in multi object trilateration.
The invention is a method and apparatus for determining the locations of a plurality of actual objects using trilateration based on the output of a plurality of range sensors. In accordance with the method and apparatus, a plurality of range measurements are obtained from a plurality of sensors, each sensor capable of providing a multiplicity of range measurements. The range measurements from the plurality of sensors are correlated with each other to generate a list of potential objects. The list of potential objects is then ordered from highest to lowest likelihood of being an actual object, for example, by ordering the objects according to a calculated cumulative error of the individual sensor measurements upon which the potential object is based. The ordered list of potential objects is then pared down to a smaller list of actual objects by selecting the potential object highest on the ordered list and assuming it is an actual object, and then removing from the list all other lower-ordered potential objects that are based on any of the measurements upon which the selected object is based. This process is then repeated for the next highest potential object remaining on the list until all potential objects on the list have either been selected as an actual object or removed from the list.